Shuchi Chawla
Abstract:
We study the makespan minimization problem with unrelated machines under the assumption that job sizes are stochastic and drawn from known distributions. The makespan objective with unrelated machines is generally considered at odds with truthfulness; Indeed Ashlagi et al. (2009) showed a linear lower bound on its truthful approximability in prior-free settings. We show that under mild distributional assumptions it is possible to circumvent this lower bound and obtain constant or sublogarithmic truthful approximations.
Our mechanisms are essentially prior-independent in that they rely on little or no information about the underlying distribution. Joint work with Jason Hartline, David Malec, and Balu Sivan.